#include "Pass.h"
#include "ComSubExprEli.h"
#include <set>
#include <algorithm>
#include <queue>
// #include <map>

typedef std::map<std::string, Value *> inst_list; //记录表达式和'='左边的值


//先bfs确定IN和OUT,再进一步进行表达式的删除与替换
//对phi的处理也值得考虑,最后替换(?),要不搞个phi_list来记录phi中可以替换的内容(?)
//用一个list来记录替换方式
//用一个list来记录删除的表达式
//phi的替换最后再检查
//现在的bfs最后还要套在一个大循环里,一直循环直到没有in和out的变化
//还要补充各个容器的初始化(每个循环结束要清空)
//考虑要不要做个代换表
//这里感觉换成unordered_map效果会更好
//考虑不用bfs，一开始直接都初始化，然后while循环一直执行for循环直到没有change
std::map<BasicBlock *, inst_list> BB_in_list;  //记录IN[B]
std::map<BasicBlock *, inst_list> BB_out_list; //记录OUT[B]
std::map<BasicBlock *, inst_list> BB_gen_list; //记录gen[B]
std::map<Value *, Value *> replace_list;       //记录替换关系

bool Flag;                                     //若改变则flag置位1

void ComSubExprEli::execute()
{
    module->set_print_name();
    /*you need to finish this function*/

    for (auto func : module->get_functions())
    {
        // if(func->get_basic_blocks().size()==0) continue;
        // ComSubExprBFS(func);//这里最后得套在一个循环中
        // ComSubExprOpt(func);
        // //phiOpt(func);
        // DeleteInst(func);
        for (auto bb : func->get_basic_blocks())
        {
            BB_in_list[bb] = inst_list();
            BB_out_list[bb] = inst_list();
            BB_gen_list[bb] = inst_list();
        }
        local_opt(func);
        global_count(func);
        global_opt(func);
    }
}

// bool ComSubExprEli::is_valid_expr(Instruction *inst) {
//     return !(inst->is_void()||inst->is_call()||inst->is_phi()||inst->is_alloca()||inst->is_load()||inst->is_cmp()||inst->is_zext());//TODO:CHECK VALID INST
// }

bool ComSubExprEli::is_cal_expr(Instruction *inst)
{ //是与计算相关的instruction
    return (inst->is_add() || inst->is_fadd() || inst->is_div() || inst->is_fdiv() || inst->is_mul() || inst->is_fmul() || inst->is_sub() || inst->is_fsub());
}

void ComSubExprEli::local_opt(Function *func)
{ //块内优化
    auto bbs = func->get_basic_blocks();

    for (auto bb : bbs)
    {
        std::vector<Instruction *> delete_list = {};
        auto insts = bb->get_instructions();
        for (auto inst : insts)
        {
            if (inst->is_void() || inst->is_call()||inst->is_gep()||inst->is_sitofp()||inst->is_fptosi()|| inst->is_phi() || inst->is_alloca() || inst->is_load() || inst->is_cmp() || inst->is_zext() || inst->is_br() || inst->is_ret())
                continue;
            std::string s;
            addrToString(inst, s);
            // std::cout << s << std::endl;
            if (BB_gen_list[bb].find(s) == BB_gen_list[bb].end())
            {
                BB_gen_list[bb].insert(std::pair<std::string, Instruction *>(s, inst));
            }
            else
            {
                inst->replace_all_use_with(BB_gen_list[bb][s]);
                delete_list.push_back(inst);
            }
        }

        for (auto inst : delete_list)
        {
            bb->delete_instr(inst);
        }
    }
}

void ComSubExprEli::global_count(Function *func){
    bool flag = true; //用来判断in和out是否发生变化
    auto bbs = func->get_basic_blocks();
    auto bb_entry = func->get_entry_block();
    for (auto bb : bbs){
        BB_out_list[bb] = BB_gen_list[bb];
    }
    int flag_1, flag_2; //flag_1判断是否是第一次循环求取交集，flag_2判断是否是while的第一次循环
    flag_1=1;
    flag_2=1;
    while (flag){
        flag = false;

        for (auto bb : bbs){
            if(flag_2) flag_1=1;
            if (bb != bb_entry){
                //inst_list tmp;
                auto bb_pre_list = bb->get_pre_basic_blocks();
                for (auto bb_pre : bb_pre_list){ //这里在取交集求in
                    if (flag_1){
                        flag_1=0;
                        BB_in_list[bb] = BB_out_list[bb_pre];
                    }
                    else{
                        for (auto inst_tmp : BB_in_list[bb]){
                            if (BB_out_list[bb_pre].find(inst_tmp.first) == BB_out_list[bb_pre].end()){
                                if(BB_gen_list[bb].find(inst_tmp.first) == BB_gen_list[bb_pre].end())
                                {
                                    BB_in_list[bb].erase(inst_tmp.first);
                                    // std::cout<<"fuck"<<std::endl;
                                    // std::cout<<inst_tmp.first<<std::endl;
                                    // std::cout<<inst_tmp.second->get_name()<<std::endl;
                                    flag=true;
                                }
                            }
                        }
                    }
                }
                for(auto inst:BB_in_list[bb]){//out原本就是egen了，这里将out和in取并集得到修改后的out
                    if(BB_out_list[bb].find(inst.first)==BB_out_list[bb].end()){
                        BB_out_list[bb].insert(inst);
                        // std::cout<<"hello"<<bb->get_name()<<std::endl;
                        // std::cout<<inst.first<<std::endl;
                        // std::cout<<inst.second->get_name()<<std::endl;
                        flag=true;
                    }
                }
                // for(auto inst:BB_out_list[bb]){
                //     for(auto bb_pre:bb->get_pre_basic_blocks()){
                //         if(BB_out_list[bb_pre].find(inst.first)!=BB_out_list[bb_pre].end()){
                            
                //         }
                //     }
                // }
            }
        }
        flag_2=0;
        // std::cout << "hello world!" << std::endl;
    }
    // for(auto bb:bbs){
    //     std::cout<<bb->get_name()<<std::endl;
    //     std::cout<<"bb_in:"<<std::endl;
    //     for(auto list_out:BB_in_list[bb]){
    //         std::cout<<list_out.first<<" "<<list_out.second->get_name()<<std::endl;
    //     }
    //     std::cout<<"bb_gen:"<<std::endl;
    //     for(auto list_out:BB_gen_list[bb]){
            
    //         std::cout<<list_out.first<<" "<<list_out.second->get_name()<<std::endl;
    //     }
    //     std::cout<<std::endl;
    // }
    // std::cout << "bye bye" << std::endl;
}

void ComSubExprEli::global_opt(Function *func){
    auto bbs=func->get_basic_blocks();
    std::vector<Instruction *> delete_list = {};
    for(auto bb:bbs){
        auto insts=bb->get_instructions();
        for(auto inst:insts){
            if (inst->is_void() || inst->is_call()||inst->is_gep()||inst->is_sitofp()||inst->is_fptosi()|| inst->is_phi() || inst->is_alloca() || inst->is_load() || inst->is_cmp() || inst->is_zext() || inst->is_br() || inst->is_ret())
                continue;
            std::string s;
            addrToString(inst,s);
            if(BB_in_list[bb].find(s)!=BB_in_list[bb].end()){
                auto replace_tmp=BB_in_list[bb].find(s)->second;
                replace_list.insert({inst,replace_tmp});
                while(replace_list.find(replace_tmp)!=replace_list.end()){
                    replace_tmp=replace_list.find(replace_tmp)->second;
                }
                // std::cout<<"replace"<<inst->get_name()<<"with"<<replace_tmp->get_name()<<std::endl;
                inst->replace_all_use_with(replace_tmp);

                delete_list.push_back(inst);
            }
        }
    }
    for(auto inst : delete_list){
        inst->get_parent()->delete_instr(inst);
    }
}
